import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:有效三角形个数、三数之和、四数之和
 * Date: 2024-02-15
 * Time:23:07
 */
public class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        int len = nums.length;
        int max = len - 1;
        for(;max >= 2;max--) {
            int mid = max - 1;
            int min = 0;
            while (min != mid) {
                if (nums[min] + nums[mid] > nums[max]) {
                    count += mid - min;
                    mid--;
                } else {
                    min++;
                }
            }
        }
        return count;
    }
///////////////////////////////////////////////////////
    public int[] twoSum(int[] price, int target) {
        int[] ret = new int[2];
        int min = 0,max = price.length - 1;
        while(min < max) {
            if(price[max] + price[min] > target) {
                max--;
            } else if(price[max] + price[min] < target) {
                min++;
            } else {
                ret[0] = price[min];
                ret[1] = price[max];
                return ret;
            }
        }
        return ret;
    }
    ///////////////////////////////////////////
    //三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);

        for(int c = nums.length - 1;c >= 2;) {
            if(nums[c] < 0)
                break;
            int a = 0;
            int b = c-1;
            while (a != b) {
                List<Integer> list = new ArrayList<>();
                if (nums[a] + nums[b] < nums[c] * (-1)) {
                    a++;
                } else if (nums[a] + nums[b] > nums[c] * (-1)) {
                    b--;
                } else {
                    list.add(nums[a]);
                    list.add(nums[b]);
                    list.add(nums[c]);
                    int tmp1 = nums[a];
                    int tmp2 = nums[b];
                    while(nums[a] == tmp1 && a != b) a++;
                    while(nums[b] == tmp2 && a != b) b--;
                    if(list.size() != 0)
                        ret.add(list);

                }
            }
            //去重
            c--;
            while(c > 0 && nums[c] == nums[c+1])
                c--;
        }
        return ret;
    }
///////////////////////////////////////////////////////////
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int a = 0;
        for(;a<nums.length;a++) {
            int b = a+1;
            for(;b<nums.length;b++) {
                int c = b+1,d = nums.length-1;
                while(c < d) {
                    long aim = (long)target - nums[a] - nums[b];
                    long sum = (long)nums[c] + nums[d];
                    if(sum < aim) {
                        c++;
                    } else if(sum >aim) {
                        d--;
                    } else {
                            ret.add(new ArrayList<>(Arrays.asList(nums[a],nums[b],nums[c],nums[d])));
                            //防止 c、d 重复
                            while (c < d && nums[c] == nums[c + 1]) c++;
                            c++;  //调整c的位置
                            while (c < d && nums[d] == nums[d - 1]) d--;
                            d--;  //调整d的位置
                    }

                }
                while(b < nums.length-1 && nums[b] == nums[b+1]) b++;
            }
            while(a < nums.length-1 && nums[a] == nums[a+1]) a++;
        }
        return ret;
    }
/*
public static List<List<Integer>> fourSum([] nums, int target) {
    List<List<Long>> ret = new ArrayList<>();
    Arrays.sort(nums);
    long a = 0;
    for(;a<nums.length;a++) {
        long b = a+1;
        for(;b<nums.length;b++) {
            long c = b+1,d = nums.length-1;
            while(c < d) {
                List<Integer> list = new ArrayList<>();

                if(nums[c] + nums[d] < target - nums[a] - nums[b]) {
                    c++;
                } else if(nums[c] + nums[d] >target - nums[a] - nums[b]) {
                    d--;
                } else {
                    list.add(nums[a]);
                    list.add(nums[b]);
                    list.add(nums[c]);
                    list.add(nums[d]);

                    //防止 c、d 重复
                    while(c < d && nums[c] == nums[c+1]) c++;
                    c++;  //调整c的位置
                    while(c < d && nums[d] == nums[d-1]) d--;
                    d--;  //调整d的位置

                    if(!list.isEmpty())
                        ret.add(list);
                }

            }
            while(b < nums.length-1 && nums[b] == nums[b+1]) b++;
        }
        while(a < nums.length-1 && nums[a] == nums[a+1]) a++;
    }
    return ret;
}
*/
///////////////////////////////////
    //长度最小的子数组
    public static int minSubArrayLen(int target, int[] nums) {
        int left = 0,right = 0;  //区间为左闭右闭
        int sum = 0;
        int len = 0;  //窗口的大小
        int minLen = nums.length+1;  //最小窗口的长度
        int flag = 0;
        for(;right < nums.length;right++) {
            sum += nums[right];
            len++;
            while(sum >= target) {
                minLen = Math.min(minLen,len);
                flag = 1;
                sum -= nums[left];
                left++;
                len--;
            }
        }

        return flag == 1 ? minLen:0;
    }
    ///////////////////////////////////////////////////
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0) return 0;
        int left = 0,right = 0;
        int len = 1;
        HashMap<Character,Integer> map = new HashMap<>();
        for(;right < s.length();right++) {
            char ch = s.charAt(right);
            if(!map.containsKey(ch)) {
                map.put(ch,right);
            } else {
                int pos = map.get(ch);
                left = pos+1;
                map.put(ch,right);
            }
            len = Math.max(len,right-left+1);
        }
        return len;
    }




}
